#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

class DSU
{
private:
    std::vector<int> parent;
    int components;

public:
    DSU(int n)
    {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int i)
    {
        if (parent[i] == i)
        {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j)
    {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj)
        {
            parent[fi] = fj;
            components--;
        }
    }

    int getComponents() const
    {
        return components;
    }
};

class Solution
{
public:
    int minTime(int n, vector<vector<int>> &edges, int k)
    {
        int low = 0, high = 1e9 + 1;
        int ans = high;
        auto check = [&](int t)
        {
            DSU dsu(n);
            for (const auto &edge : edges)
            {
                if (edge[2] > t)
                {
                    dsu.unite(edge[0], edge[1]);
                }
            }
            return dsu.getComponents() >= k;
        };

        while (low <= high)
        {
            int mid = low + (high - low) / 2;
            if (check(mid))
            {
                ans = mid;
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }

        return ans;
    }
};